package com.adaydayup.week4;

/**
 * 乘法表中第 K 小的数
 * 输入: m = 3, n = 3, k = 5
 * 输出: 3
 * 解释:
 * 乘法表:
 * 1	2	3
 * 2	4	6
 * 3	6	9

 */
public class FindKthNumber668 {
    public static int findKthNumber668(int m,int n,int k){
        int l=1,r=m*n;
        while (l<r){
            int mid=l+(r-l)/2;
            int count = count(m, n, mid);
            if (count>=k){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        return l;
    }

    //统计乘法表中有多少个等于K的数目
    private static int count(int m, int n, int k) {
       int res=0;
       //统计每行小于等于K的数目
        for (int i = 1; i <=m; ++i) {
            res=res+Math.min(k/i,n);
        }
        return res;
    }

    public static void main(String[] args) {
        int res = findKthNumber668(3, 3, 5);
        System.out.println(res);
    }

}
